10849. Двигаем слона

 

Рассмотрим шахматную доску размером n ´ n, на которой находится только одна фигура: слон. Необходимо найти минимальное количество ходов, за которое слон может попасть из одной клетки в другую.

 

Вход. Первая строка содержит количество групп тестов c. Первая строка каждого теста содержит число запросов t, 1 £ t £ 100. Вторая строка теста содержит размер доски n, 1 £ n £ 108. Далее следуют t запросов, состоящих из начального и конечного положений слона. Положение слона задается его x и y координатой на доске.

 

Выход. Для каждого теста вывести минимальное количество ходов, за которое слон может попасть из начальной клетки в конечную.

 

Пример входа

Пример выхода

2

 

3

8

3 6 6 3

4 2 2 3

7 2 1 4

 

2

6

1 2 6 5

2 3 5 1

1

no move

2

2

no move

 

 

РЕШЕНИЕ

шахматы

 

Анализ алгоритма

Пусть (x1, z1) – начальное, (x2, z2) – конечное положение слона. Если начальные и конечные координаты совпадают, то слону следует совершить 0 ходов (ходить не следует). Если начальная и конечная клетки имеют разный цвет, то требуемого пути у слона не существует (суммы x1 + z1 и x2 + z2 имеют разную четность). Если  начальная и конечная клетки находятся на одной диагонали ( |x1 – x2| = |z1 – z2| ), то слону достаточно совершить один ход. Иначе слон всегда за два шага может попасть из начального поля в конечное.

 

Пример

Рассмотрим первый блок тестов. Доска имеет размер 8 ´ 8. Из позиции (3, 6) в позицию (5, 4) можно попасть за 1 ход, так как |3 – 5| = |6 – 4|. Из позиции (4, 2) в (2, 3) пути для слона не существует, так как эти клетки имеют разный цвет.

 

Реализация алгоритма

Читаем число тестовых блоков tests. Для каждого блока вводим количество запросов t и размер доски n.

 

scanf("%d",&tests);

while(tests--)

{

  scanf("%d %d",&t,&n);

 

Начальное положение слона храним в (x1, z1), конечное – в (x2, z2). В соответствии с выше изложенными в анализе алгоритма правилами, вычисляем требуемое количество ходов для слона.

 

  while(t--)

  {

    scanf("%d %d %d %d",&x1,&z1,&x2,&z2);

    if ((x1 == x2) && (z1 == z2)) printf("0\n"); else

    if ((x1 + z1 + x2 + z2) % 2) printf("no move\n");

    else if (abs(x1 - x2) == abs(z1 - z2)) printf("1\n");

    else printf("2\n");

  }

}